package leetcode.trietree.common;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class TrieTreeUtils {
    public static int prefixCount(String[] words, String pref) {
        // 字典树前期准备
        List<Map<Character, Integer>> nodes = new ArrayList<>();
        Map<Character, Integer> rootNode = new HashMap<>();
        nodes.add(rootNode);
        Map<Character, Integer> curNode = rootNode;
        Integer sonNodeIndex = null;
        Map<Integer, Integer> nums = new HashMap<>();

        int len = pref.length();

        // 构建字典树
        for (String curStr : words) {
            if(curStr.length() < len){
                continue;
            }
            for (int i = 0; i < len; i++) {
                Character c = curStr.charAt(i);
                sonNodeIndex = curNode.get(c);
                if (sonNodeIndex == null) {
                    Map<Character, Integer> sonNode = new HashMap<>();
                    nodes.add(sonNode);
                    sonNodeIndex = nodes.size() - 1;
                    curNode.put(c, sonNodeIndex);
                    curNode = sonNode;
                } else {
                    curNode = nodes.get(sonNodeIndex);
                }
                nums.merge(sonNodeIndex, 1, Integer::sum);
            }
            curNode = rootNode;
        }

        // 查询字典树
        for (int i = 0; i < pref.length(); i++) {
            Character c = pref.charAt(i);
            sonNodeIndex = curNode.get(c);
            if (sonNodeIndex == null) {
                return 0;
            } else {
                curNode = nodes.get(sonNodeIndex);
            }
        }
        return nums.get(sonNodeIndex);
    }

    public static boolean wordBreak(String s, List<String> wordDict) {
        TrieNode root = buildTrieTree(wordDict);
        TrieNode curNode = root;
        for(int i = 0; i< s.length(); i++){
            Character c = s.charAt(i);
            TrieNode childNode = curNode.next.get(c);
            if(childNode == null){
                curNode = root;
            }





        }


        return true;
    }

    private static TrieNode buildTrieTree(List<String> wordDict) {
        TrieNode root = new TrieNode();
        TrieNode curNode = root;
        for(String word : wordDict){
            for(int i = 0; i< word.length(); i++){
                Character c = word.charAt(i);
                TrieNode child = new TrieNode();
                curNode.next.putIfAbsent(c, child);
                if(i == word.length() -1){
                    child.end ++;
                }
            }
        }
        return root;
    }
}
